/**
 * 给定每个房屋存放金额的数组,计算在不触发警报的情况下能偷的最大金额
 * 相邻房屋被偷会触发警报
 * @param {number[]} nums
 * 动态规划 
 */
var rob = function (nums) {
    if (nums.length === 0) {
        return 0
    }
    if (nums.length === 1) {
        return nums[0]
    }

    // 记录每个点能偷到的最大金额
    const memo = []
    memo[0] = nums[0]
    memo[1] = Math.max(nums[0], nums[1])
    for (let i = 2; i < nums.length; i++) {
        // 比较 偷当前+前2个能偷的最大值 和 前1个能偷的最大值
        memo[i] = Math.max(nums[i] + memo[i - 2], memo[i - 1])
    }

    return memo[nums.length - 1]
}

// 优化空间复杂度
var rob1 = function (nums) {
    if (nums.length === 0) {
        return 0
    }
    if (nums.length === 1) {
        return nums[0]
    }

    // 只记录能偷到的最大金额和次大金额
    let prev1 = nums[0]
    let prev2 = Math.max(nums[0], nums[1])
    for (let i = 2; i < nums.length; i++) {
        // 比较 偷当前+前2个能偷的最大值 和 前1个能偷的最大值
        const temp = Math.max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = temp
    }

    return prev1
}